A database management system (DBMS) is computer software that stores data and provides software routines for manipulating the stored data. A DBMS may be used directly (i.e., by human users), as a component of another software package, or to provide service to another software package.
A database is a collection of data which is stored and managed as a unit by a DBMS. A "relational database" is a database which contains tables that are used to store sets of data and to specify relationships between the different sets of data stored in the database. Relational databases and database management systems are widely used in the prior art. Therefore this document will describe prior art database systems only to the extent necessary to point out the differences between such prior art systems and the present invention.
Typically, databases are used to store sets of related data. For example, a database may be used to store all the seat reservations made by the customers of an airline, plus information about the airplane (e.g., seating chart information), information about the customers (e.g., address, credit card used to purchase tickets, and travel agent), and so on. This is an example of a database which is well suited for a prior art relational database management system.
The reason that the airline seat reservation database is easy to use with prior art database technology is that the data is easily organized as a set of flat records, in the form of a few tables: one for seat reservations, one for customer information, and so on.
An example of a set of data that is "difficult" to efficiently store and manipulate in a prior art relational database is shown in FIG. 1. This set of data 100, which denotes a set of automobile parts and also denotes which parts are components of other parts, is herein called a "directed graph". The data structures conventionally used to store such sets of data in computers are called "directed graph data structures". The reason that a directed graph is "difficult" to handle with a conventional database system is that while this data can be stored in and retrieved from a conventional database table, it is awkward to do so.
FIG. 2 contains a typical prior art table 110 (herein called the ContainsParts table) that would be used by a prior art database management system to store the directed graph shown in FIG. 1. FIG. 2 also shows a second table 120 (herein called the Parts table) which contains cost data for automobile parts. By using the two tables 110 and 120 together, one can determine the relative costs of manufacturing various portions of an automobile.
While table 110 in FIG. 2 contains all the data needed to reconstruct the directed graph of FIG. 1, it is very awkward for a prior art database management system to utilize data which is organized in this fashion. For example, consider the steps which would need to be performed by the prior art DBMS to generate a directed graph representing the set of all components of the engine. To do this, we would first have to examine all the records with a partName of ENGINE to generate a first list of engine parts. Then we would have to examine all the records for the parts identified in this first search (i.e., with partName equal to CAM SHAFT or WATER JACKET OR CYLINDER 1, etc.). In a real life example, we would then have to examine all the records for the parts identified in the second search, and so on.
In terms of search commands using SQL, the industry standard language for querying databases, a separate query would be required for retrieving each set of subparts. As will be explained in more detail below, to regenerate the portion of the directed graph corresponding to ENGINE, one would have to perform literally dozens of queries. TABLE 1 lists the fifty-four SQL queries which would be required to regenerate the entire directed graph for AUTOMOBILE:
TABLE 1 __________________________________________________________________________ PRIOR ART QUERIES FOR RETRIEVING DIRECTED GRAPH __________________________________________________________________________ 1) SELECT * FROM ContainsParts WHERE PARTNAME = "AUTOMOBILE" 2) SELECT * FROM ContainsParts WHERE PARTNAME = "BODY" 3) SELECT * FROM ContainsParts WHERE PARTNAME = "FRAME" 4) SELECT * FROM ContainsParts WHERE PARTNAME = "POWER TRAIN" 5) SELECT * FROM ContainsParts WHERE PARTNAME = "DASH BOARD" 6) SELECT * FROM ContainsParts WHERE PARTNAME = "SEATS" 7) SELECT * FROM ContainsParts WHERE PARTNAME = "SHELL" 8) SELECT * FROM ContainsParts WHERE PARTNAME = "WINDSHIELD" 9) SELECT * FROM ContainsParts WHERE PARTNAME = "DIFFERENTIAL" 10) SELECT * FROM ContainsParts WHERE PARTNAME = "DRIVE SHAFT" 11) SELECT * FROM ContainsParts WHERE PARTNAME = "ENGINE" 12) SELECT * FROM ContainsParts WHERE PARTNAME = "TRANSMISSION" 13) SELECT * FROM ContainsParts WHERE PARTNAME = "CAM SHAFT" 14) SELECT * FROM ContainsParts WHERE PARTNAME = "CYLINDER 1" 15) SELECT * FROM ContainsParts WHERE PARTNAME = "CYLINDER 2" 16) SELECT * FROM ContainsParts WHERE PARTNAME = "CYLINDER 3" 17) SELECT * FROM ContainsParts WHERE PARTNAME = "CYLINDER 4" 18) SELECT * FROM ContainsParts WHERE PARTNAME = "CYLINDER 5" 19) SELECT * FROM ContainsParts WHERE PARTNAME = "CYLINDER 6" 20) SELECT * FROM ContainsParts WHERE PARTNAME = "CYLINDER 7" 21) SELECT * FROM ContainsParts WHERE PARTNAME = "CYLINDER 8" 22) SELECT * FROM ContainsParts WHERE PARTNAME = "WATER JACKET" 23) SELECT * FROM ContainsParts WHERE PARTNAME = "PISTON 1" 24) SELECT * FROM ContainsParts WHERE PARTNAME = "PISTON 2" 25) SELECT * FROM ContainsParts WHERE PARTNAME = "PISTON 3" 26) SELECT * FROM ContainsParts WHERE PARTNAME = "PISTON 4" 27) SELECT * FROM ContainsParts WHERE PARTNAME = "PISTON 5" 28) SELECT * FROM ContainsParts WHERE PARTNAME = "PISTON 6" 29) SELECT * FROM ContainsParts WHERE PARTNAME = "PISTON 7" 30) SELECT * FROM ContainsParts WHERE PARTNAME = " PISTON 8" 31) SELECT * FROM ContainsParts WHERE PARTNAME = "SPARK PLUG 1" 32) SELECT * FROM ContainsParts WHERE PARTNAME = "SPARK PLUG 2" 33) SELECT * FROM ContainsParts WHERE PARTNAME = "SPARK PLUG 3" 34) SELECT * FROM ContainsParts WHERE PARTNAME = "SPARK PLUG 4" 35) SELECT * FROM ContainsParts WHERE PARTNAME = "SPARK PLUG 5" 36) SELECT * FROM ContainsParts WHERE PARTNAME = "SPARK PLUG 6" 37) SELECT * FROM ContainsParts WHERE PARTNAME = "SPARK PLUG 7" 38) SELECT * FROM ContainsParts WHERE PARTNAME = "SPARK PLUG 8" 39) SELECT * FROM ContainsParts WHERE PARTNAME = "EXHAUST VALVE 1" 40) SELECT * FROM ContainsParts WHERE PARTNAME = "EXHAUST VALVE 2" 41) SELECT * FROM ContainsParts WHERE PARTNAME = "EXHAUST VALVE 3" 42) SELECT * FROM ContainsParts WHERE PARTNAME = "EXHAUST VALVE 4" 43) SELECT * FROM ContainsParts WHERE PARTNAME = "EXHAUST VALVE 5" 44) SELECT * FROM ContainsParts WHERE PARTNAME = "EXHAUST VALVE 6" 45) SELECT * FROM ContainsParts WHERE PARTNAME = "EXHAUST VALVE 7" 46) SELECT * FROM ContainsParts WHERE PARTNAME = "EXHAUST VALVE 1" 47) SELECT * FROM ContainsParts WHERE PARTNAME = "INTAKE VALVE 1" 48) SELECT * FROM ContainsParts WHERE PARTNAME = "INTAKE VALVE 2" 49) SELECT * FROM ContainsParts WHERE PARTNAME = "INTAKE VALVE 3" 50) SELECT * FROM ContainsParts WHERE PARTNAME = "INTAKE VALVE 4" 51) SELECT * FROM ContainsParts WHERE PARTNAME = "INTAKE VALVE 5" 52) SELECT * FROM ContainsParts WHERE PARTNAME = "INTAKE VALVE 6" 53) SELECT * FROM ContainsParts WHERE PARTNAME = "INTAKE VALVE 7" 54) SELECT * FROM ContainsParts WHERE PARTNAME = "INTAKE VALVE __________________________________________________________________________ 8"
By way of comparison, the present invention allows a person or program to retrieve an entire subtree (or even a pruned subtree) of a directed graph using a single query. The single query needed to retrieve the entire directed graph in the preferred embodiment of the present invention is:
______________________________________ SELECT * FROM ContainsParts EXPAND ContainsParts(*) WHERE PARTNAME = "AUTOMOBILE" ______________________________________
The single query which would retrieve all portions of the directed graph corresponding to ENGINE is:
______________________________________ SELECT * FROM ContainsParts EXPAND ContainsParts(*) WHERE PARTNAME = "ENGINE" ______________________________________
Trees and other directed graph data structures are commonly used in scientific and engineering applications to represent and store data. Because of the limitations in the prior art, these types of scientific and engineering data are typically not stored using database management systems. As a result, all of the well developed tools associated with database management systems are generally not available to the users of scientific and engineering data. Instead, such data is typically stored and manipulated using a wide variety of special software programs. These programs vary widely in their manner of operation, how they represent data internally, and so on. Unlike relational database management systems, the programs each have a different theory of operation and each tends to be used by only a small market niche.
The primary goal of the present invention is to enable scientific and engineering data, which is normally stored in the form of tree data structures or directed graph data structures in operating system files (i.e., files directly accessed by application programs), to be easily stored and manipulated in a relational database management system. From another perspective, the primary goal of the present invention is to modify conventional relational database management systems so as to efficiently and intelligently handle data which is logically organized as a directed graph.
An important property of the present invention that is not provided by prior art relational database management systems is "transitive closure". Transitive closure means the ability to follow the links in a directed graph data structure and to process an entire or specified portion of a tree or directed graph as single entity. Database management systems which include the features of the present invention perform transitive closures, whereas prior art relational database management systems do not.